package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/10 5:58 下午
 * @see
 */
public class SortArrayByIncreasingFrequency {

    /**
     * 暴力逻辑解法
     *
     * @param nums
     * @return
     */
    public int[] frequencySort(int[] nums) {
        int len = nums.length;
        int range = 201;
        int[] dp = new int[range];
        for (int i = 0; i < len; i++) {
            dp[nums[i] + 100]++;
        }
        /**
         * countToNum key为数字出现的数量、value为出现该数量的数字列表，并且是升序排序
         */
        TreeMap<Integer, List<Integer>> countToNum = new TreeMap<>();
        for (int i = 0; i < range; i++) {
            if (dp[i] != 0) {
                List<Integer> orDefault = countToNum.getOrDefault(dp[i], new ArrayList<>(2));
                orDefault.add(i - 100);
                countToNum.put(dp[i], orDefault);
                System.out.println("dp[i] = " + dp[i] + " i = " + i);
            }
        }
        int tag = 0;
        for (Integer key : countToNum.keySet()) {
            List<Integer> numbers = countToNum.get(key);
            if (numbers != null && !numbers.isEmpty()) {
                // 匿名内部类写法
//                Collections.sort(numbers, new Comparator<Integer>() {
//                    @Override
//                    public int compare(Integer o1, Integer o2) {
//                        if (o1 > o2) return -1;
//                        if (o1 < o2) return 1;
//                        return 0;
//                    }
//                });

                if (numbers.size() > 1) {
                    // lambad 表达式写法
                    Collections.sort(numbers, (first, second) -> {
                        if (first > second) return -1;
                        if (first < second) return 1;
                        return 0;
                    });
                }

                for (Integer number : numbers) {
                    for (Integer i = 0; i < key; i++) {
                        nums[tag++] = number;
                    }
                }
            }
        }
        return nums;
    }


    /**
     * 面向对象解法
     *
     * @param nums
     * @return
     */
    public int[] frequencySort2(int[] nums) {
        int len = nums.length;
        HashMap<Integer, Number> numbers = new HashMap<>();
        Number number, orDefault;
        for (int i = 0; i < len; i++) {
            number = new Number(nums[i], 0);
            orDefault = numbers.getOrDefault(nums[i], number);
            orDefault.incrementCount();
            numbers.put(nums[i], orDefault);
        }
        TreeSet<Number> resultNumbers = new TreeSet<>();
        for (Integer key : numbers.keySet()) {
            resultNumbers.add(numbers.get(key));
        }
        int tag = 0;
        for (Number resultNumber : resultNumbers) {
            for (int i = 0; i < resultNumber.count; i++) {
                nums[tag++] = resultNumber.value;
            }
        }

        return nums;
    }

    class Number implements Comparable<Number> {
        int value;
        int count;

        public Number(int value, int count) {
            this.value = value;
            this.count = count;
        }

        public void incrementCount() {
            this.count++;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Number number = (Number) o;
            return value == number.value;
        }

        @Override
        public int hashCode() {
            return Objects.hash(value);
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        @Override
        public int compareTo(Number o) {
            if (this.count > o.count) return 1;
            if (this.count < o.count) return -1;
            if (this.value > o.value) return -1;
            if (this.value < o.value) return 1;
            return 0;
        }
    }
}
